package algorthm.systemTraning.binaryTree;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.io.IOException;
import java.util.Deque;
import java.util.LinkedList;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @className: ISFBT
 * @Description:
 * @Author: wangyifei
 * @Date: 2024/4/6 14:51
 */
public class ISFBT {
    private static Logger logger = LoggerFactory.getLogger(ISFBT.class);

    /**
     * 判断是否满二叉树
     * 1.分析从左右两个孩子要什么东西
     *   1) 要 head ，则要 head.left,head.right 都是完全二叉树, 并且高度相等。
     *   2）不要 head , 则左右孩子都其中不是完全二叉树，或者高度不相等。
     * 2. 设计 Info  Info{int height , int isFull}
    * */
    public static void main(String[] args) throws IOException {

        Drawing d = new Drawing();
        for (int i = 0; i < 9000; i++) {
            int maxLevel = (int)Math.random()*10;
            Node head = generateRandomTree(maxLevel, 100);
            boolean rs = isFull2(head);
            boolean rs1 = isFullBinaryTree(head);
            if(rs != rs1){
                System.out.println("Oops");
                d.drawEntrance(head);
                MaxSubBST.printFromTopToBottom(head);
                break;
            }
        }
        System.out.println("ok");
    }
    public static boolean isFull2(Node head){
       if(null == head){
          return true ;
       }
        Info info = process(head);
        return info.isFull ;
    }
    public static Info process(Node head){
        if(null == head){
            return new Info( 0  , true);
        }
        boolean isFull = true ;
        int height = 1 ;
        Info L = process(head.left);
        Info R = process(head.right);
        if(null != L){
            height = Math.max(height + 1 , L.height);
        }
        if(null != R){
            height = Math.max(height + 1 , R.height);
        }
        if(null != L && !L.isFull){
            isFull = false ;
        }
        if(null != R && !R.isFull){
            isFull = false ;
        }
        if(null != L && null != R && R.height != L.height){
            isFull = false ;
        }
        return new Info(height , isFull);
    }
    public static class Info{
        public int height ;
        public boolean isFull ;
        public Info(int h, boolean i){
           height = h ;
           isFull = i ;
        }
    }
    public static boolean isFullBinaryTree(Node head){
        if(null == head){
           return true ;
        }
        int sum = 0 ;
        int height = 0;
        Deque<Node> queue = new LinkedList<>();
        queue.addLast(head);
        while(!queue.isEmpty()){
            height++;
            Deque<Node> q = new LinkedList<>();
            while(!queue.isEmpty()){
                Node node = queue.pollFirst();
                sum++;
                if(null != node.left){
                    q.addLast(node.left);
                }
                if(null != node.right){
                    q.addLast(node.right);
                }
            }
            queue = q ;
        }

        return sum == (Math.pow(2 , height) - 1);
    }
    public static Node generateRandomTree(int maxLevel, int maxValue)
    {
        return generate(1, maxLevel, maxValue);
    }
    public static Node generate(int level, int maxLevel, int maxValue)
    {
        if (level > maxLevel || Math.random() < 0.5)
        {
            return null;
        }
        Node head = new Node((int) (Math.random() * maxValue));
        head.left = generate(level + 1, maxLevel, maxValue);
        head.right = generate(level + 1, maxLevel, maxValue);
        return head;
    }
}
